import java.util.*;

public class C_1874 {
    static int min;
    static int num;
    public static void main(String[] args) {
        min = 100000;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<Set<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new HashSet<>());
        }
        for (int i = 0; i < m; i++) {
            int t1 = sc.nextInt()-1;
            int t2 = sc.nextInt()-1;
            list.get(t1).add(t2);
            list.get(t2).add(t1);
        }
        num = n-1;
        List<Set<Integer>> l = new ArrayList<>();
        l.add(new HashSet<>());
        l.get(0).add(0);
        dfs(l,list,0,0);
        System.out.println(min);
    }
    static void dfs(List<Set<Integer>> l,List<Set<Integer>> list,int ren,int js){
        if (ren==num+1){
            min = Math.min(min,l.size());
            return;
        }
        if (js>=min)
            return;
        if (check(l,list,ren,js))
            l.get(js).add(ren);
        else return;
        ren++;
        for (int i = 0; i < l.size(); i++) {
            dfs(l,list,ren,i);
            l.get(js).remove(ren);
        }
        l.add(new HashSet<>());
        int t = l.size()-1;
        dfs(l,list,ren,l.size()-1);
        l.remove(t);
    }
    static boolean check(List<Set<Integer>> l, List<Set<Integer>> list, int ren, int js){
        for (Integer integer : l.get(js)) {
            if(list.get(ren).contains(integer))
                return false;
        }
        return true;
    }
}
